/*
 * Copyright 2003 Program of Computer Graphics, Cornell University
 *     580 Rhodes Hall
 *     Cornell University
 *     Ithaca NY 14853
 * Web: http://www.graphics.cornell.edu/
 * 
 * Not for commercial use. Do not redistribute without permission.
 */
#include "stdafx.h"

#include "KDSplits.h"
#include "BriteDefs.h"

void KDAllSplitEstimator::initialize(const AxisAlignedBox &_bounds) {
  bounds = _bounds;
  boundsBig = _bounds;
  //compute an epsilon to enlarge bounds by so that round-off error does not
  //fool us into thinking we can split more precisely than we really can
  eps = bounds.computeEpsilon();
  
  F32vec4 temp(EPSM_BIG);
  temp *= eps;
  boundsBig.expandBy(temp);
  
  eps = F32vec4(EPSM_ESTIMATE)*eps;
  //now clear all counts to zero
  totalTri = 0;
  totalOther = 0;
  numEvents = 0;
}

void KDAllSplitEstimator::addTri(int count, const AxisAlignedBox &box) 
{
  assert(count < 256);
  F32vec4 min = box.min-eps;
  F32vec4 max = box.max+eps;
  xEvents[numEvents].setTri(min[0],count,0);
  xEvents[numEvents+1].setTri(max[0],0,count);
  yEvents[numEvents].setTri(min[1],count,0);
  yEvents[numEvents+1].setTri(max[1],0,count);
  zEvents[numEvents].setTri(min[2],count,0);
  zEvents[numEvents+1].setTri(max[2],0,count);
  numEvents += 2;
  totalTri += count;
}

void KDAllSplitEstimator::addOther(int count, const AxisAlignedBox &box) 
{
  assert(count < 256);
  F32vec4 min = box.min-eps;
  F32vec4 max = box.max+eps;
  xEvents[numEvents].setOther(min[0],count,0);
  xEvents[numEvents+1].setOther(max[0],0,count);
  yEvents[numEvents].setOther(min[1],count,0);
  yEvents[numEvents+1].setOther(max[1],0,count);
  zEvents[numEvents].setOther(min[2],count,0);
  zEvents[numEvents+1].setOther(max[2],0,count);
  numEvents += 2;
  totalOther += count;
}

static F32vec1 median3(const F32vec1 &a, const F32vec1 &b, const F32vec1 &c) {
  //median can be found by the max of 3 pairwise mins
  F32vec1 median = simd_max(simd_min(a,b),simd_max(simd_min(b,c),simd_min(c,a)));
  return median;
}

static void quickSortEvents(KDACompactEvent *src, int start, int end) {
  //we sort in ascending order using an optimized quicksort
  int len = end - start;
  if (len < 40) {
    assert(sizeof(*src)==8);
    F32vec4 cur = _mm_setzero_ps();  //we actually only use the low 8bytes of these two variables
    F32vec4 tmpa = _mm_setzero_ps();
    F32vec4 tmpb = _mm_setzero_ps();
    F32vec4 tmpc = _mm_setzero_ps();
    //just use a simple insertion sort for small arrays
    for (int i=start+1; i<end; i++) {
      int j = i;
      cur = _mm_loadl_pi(cur,(__m64 *)&src[i]);
      tmpa = _mm_loadl_pi(tmpa,(__m64 *)&src[j-1]);
      tmpb = _mm_loadl_pi(tmpb,(__m64 *)&src[j-2]);
      //this loop has been unrolled twice and modulo scheduled to reduce branches and hide latency
      while(j>start+2) {
        tmpc = _mm_loadl_pi(tmpc,(__m64 *)&src[j-3]);
        if (!_mm_ucomigt_ss(F32vec1(tmpa),F32vec1(cur))) goto insert_cur;
        _mm_storel_pi((__m64 *)&src[j],tmpa);
        j--;
        tmpa = _mm_loadl_pi(tmpa,(__m64 *)&src[j-3]);
        if (!_mm_ucomigt_ss(F32vec1(tmpb),F32vec1(cur))) goto insert_cur;
        _mm_storel_pi((__m64 *)&src[j],tmpb);
        j--;
        tmpb = _mm_loadl_pi(tmpb,(__m64 *)&src[j-3]);
        if (!_mm_ucomigt_ss(F32vec1(tmpc),F32vec1(cur))) goto insert_cur;
        _mm_storel_pi((__m64 *)&src[j],tmpc);
        j--;
      }
      //handle case when start < j < start+2
      while(j>start) {
        if (!_mm_ucomigt_ss(F32vec1(tmpa),F32vec1(cur))) break;
        _mm_storel_pi((__m64 *)&src[j],tmpa);
        j--;
        tmpa = _mm_loadl_pi(tmpa,(__m64 *)&src[j-1]);
      }
insert_cur:
      _mm_storel_pi((__m64 *)&src[j],cur);
//      KDACompactEvent cur = src[i];
//      F32vec1 curVal = cur.value;
//      while((j>start)&&(_mm_ucomigt_ss(F32vec1(src[j-1].value),curVal))) {
//        src[j] = src[j-1];
//        j--;
//      }
//      src[j] = cur;
    }
  } else {
    //its a quicksort, first choose the partitioning value
    F32vec1 pVal;
    if (len > 40) { //for large arrays choose pseudomedian of 9
      int s = len>>3;
      pVal = median3(median3(F32vec1(src[start].value),
                             F32vec1(src[start+s].value),
                             F32vec1(src[start+2*s].value)),
                     median3(F32vec1(src[start+3*s].value),
                             F32vec1(src[start+4*s].value),
                             F32vec1(src[end-3*s].value)),
                     median3(F32vec1(src[end-2*s].value),
                             F32vec1(src[end-s].value),
                             F32vec1(src[end-1].value)));
      //the explicit calls for F32vec1() prevent compiler from 
      //incorrectly doing a float->int->float conversion
    } else { //for intermediate arrays use median of 3 elements
      pVal = median3(F32vec1(src[start].value), 
                     F32vec1(src[(start+end)>>1].value), 
                     F32vec1(src[end-1].value));
    }
    //now split the array into four sections as follows
    // (==pVal) (<pVal) (>pVal) (==pVal)
	int a = start, b = a, c = end - 1, d = c;
    KDACompactEvent swap;
    
    for(;;) {
      for(;;) {
        F32vec1 testb = F32vec1(src[b].value);
        if (b > c) goto outer_loop_exit;   //break out of both nested for loops
        if (_mm_ucomigt_ss(testb,pVal)) break;
        if (_mm_ucomieq_ss(testb,pVal)) {
          swap = src[a];
          src[a++] = src[b];
          src[b] = swap;
        }
        b++;
      }
      for(;;) {
        F32vec1 testc = F32vec1(src[c].value);
        if (b > c) goto outer_loop_exit;   //break out of both nested for loops
        if (_mm_ucomilt_ss(testc,pVal)) break;
        if (_mm_ucomieq_ss(testc,pVal)) {
          swap = src[d];
          src[d--] = src[c];
          src[c] = swap;
        }
        c--;
      }
      swap = src[b];
      src[b++] = src[c];
      src[c--] = swap;
    }
    
outer_loop_exit:
    // Swap values == pVal back to center
    for(int i=start;i<a;i++) {
      b--;
      swap = src[i];
      src[i] = src[b];
      src[b] = swap;
    }
    for(int k=d+1;k<end;k++) {
      c++;
      swap = src[k];
      src[k] = src[c];
      src[c] = swap;
    }
    quickSortEvents(src, start, b);
    quickSortEvents(src, c+1, end);
  }
}

int KDAllSplitEstimator::prepareEvents(KDACompactEvent *src, float min, float max)
{
  quickSortEvents(src,0,numEvents);
  /*
  //check to see that the array was sorted properly
  for(int i=1;i<numEvents;i++) {
    if (src[i-1].value > src[i].value) {
_asm int 3;
    }
  }
  */
  /*
  //first we sort the source events
  //since we assume total number of events will be small
  //we just use a simple n^2 selection sort
  for(int i=0;i<numEvents-1;i++) {
    int smallestIndex = i;
    F32vec1 smallestValue = src[i].value;
    for(int j=i+1;j<numEvents;j++) {
      F32vec1 test = src[j].value;
      if (_mm_ucomilt_ss(test,smallestValue))
        smallestIndex = j;
      smallestValue = simd_min(smallestValue,test);
//    code above turned out to be faster than this version
//      if (src[j].value < smallestValue) {
//        smallestIndex = j; smallestValue = src[j].value; 
//      }
    }
    KDACompactEvent temp = src[i];
    src[i] = src[smallestIndex];
    src[smallestIndex] = temp;
  }
  */
  //now transform into sets of valid events that lie within
  //specified bounds, include explicit left and right counts
  int leftTri=0,rightTri=totalTri;
  int leftOther=0,rightOther=totalOther;
  int k=0;
  int numOutEvents=0;
  for(;k<numEvents;k++) {
    if (src[k].value > min) break;
    leftTri += src[k].dLeftTri;
    rightTri -= src[k].dRightTri;
    leftOther += src[k].dLeftOther;
    rightOther -= src[k].dRightOther;
  }
  while(k<numEvents) {
    if (src[k].value > max) break;
    int repEnd = k+1;
    //compress multiple events with same value into a single event
    //for multiple coincident events we will have repEnd > k+1
    for(;repEnd<numEvents;repEnd++) {
      if (src[repEnd].value != src[k].value) break;
    }
    for(int m=k;m<repEnd;m++) {
      rightTri -= src[m].dRightTri;
      rightOther -= src[m].dRightOther;
    }
    event[numOutEvents++].set(src[k].value,leftTri,rightTri,leftOther,rightOther);
    for(int p=k;p<repEnd;p++) {
      leftTri += src[p].dLeftTri;
      leftOther += src[p].dLeftOther;
    }
    k = repEnd;
  }
  return numOutEvents;
}

int KDAllSplitEstimator::prepareXEvents() {
  if (bounds.max[0]-bounds.min[0]<26*eps[0]) return 0;
  return prepareEvents(xEvents,bounds.min[0]+eps[0],bounds.max[0]-eps[0]);
}

int KDAllSplitEstimator::prepareYEvents() {
  if (bounds.max[1]-bounds.min[1]<26*eps[1]) return 0;
  return prepareEvents(yEvents,bounds.min[1]+eps[1],bounds.max[1]-eps[1]);
}

int KDAllSplitEstimator::prepareZEvents() {
  if (bounds.max[2]-bounds.min[2]<26*eps[2]) return 0;
  return prepareEvents(zEvents,bounds.min[2]+eps[2],bounds.max[2]-eps[2]);
}


/**************KDFixedSplitsEstimator***********************/

static void setFloatArray(float value, float *ptr, int count) {
  if (count > 8) {
    F32vec4 v_value(value);
    //first we must get to a point where ptr is 16byte aligned
    LONG_PTR alignCount4 = (-(LONG_PTR)ptr)&0x0F;
    for(int i=0;i<alignCount4;i+=4) {
      *ptr++ = value;
      count--;
    }
    //now store vectors of four float to fill up array
    while(count>=16) {
      Store_F32vec4(ptr,v_value);
      Store_F32vec4(ptr+4,v_value);
      Store_F32vec4(ptr+8,v_value);
      Store_F32vec4(ptr+12,v_value);
      ptr += 16;
      count -= 16;
    }
    while(count>=4) {
      Store_F32vec4(ptr,v_value);
      ptr += 4;
      count -= 4;
    }
  }
  //fill any remaining unset positions in the array
  while(count>0) {
    *ptr++ = value;
    count--;
  }
}

void KDFixedSplitEstimator::initialize(const AxisAlignedBox &_bounds) { 
  bounds = _bounds;
  boundsBig = _bounds;
  //compute an epsilon to enlarge bounds by so that round-off error does not
  //fool us into thinking we can split more precisely than we really can
  eps = bounds.computeEpsilon();
  
  F32vec4 temp(EPSM_BIG);
  temp *= eps;
  boundsBig.expandBy(temp);
  
  eps = F32vec4(EPSM_ESTIMATE)*eps;
  //compute transform to axis aligned splitting planes in each direction
  b[0] = float(KDFIXEDSPLIT_NUM) / (bounds.max[0] - bounds.min[0]);
  b[1] = float(KDFIXEDSPLIT_NUM) / (bounds.max[1] - bounds.min[1]);
  b[2] = float(KDFIXEDSPLIT_NUM) / (bounds.max[2] - bounds.min[2]);
  b[3] = 0;

  //now clear all counts to zero
  totalTri = 0;
  totalOther = 0;
  //12 arrays for leftTriX,leftTriY,leftTriZ,rightTriX,rightTriY,rightTriZ,leftOtherX, etc.
  setFloatArray(0,(float*)(this->leftTriX),12*(KDFIXEDSPLIT_NUM+1));
  //then reset left events to FLT_MAX
  setFloatArray(FLT_MAX,this->leftEventX,3*(KDFIXEDSPLIT_NUM+1));
  //then reset right events to -FLT_MAX
  setFloatArray(-FLT_MAX,this->rightEventX,3*(KDFIXEDSPLIT_NUM+1));
  //a few debug asserts to check that we did it right
  assert(leftTriX[0]==0);
  assert(rightTriZ[KDFIXEDSPLIT_NUM]==0);
  assert(rightOtherZ[KDFIXEDSPLIT_NUM]==0);
  assert(leftEventZ[KDFIXEDSPLIT_NUM]==FLT_MAX);
  assert(rightEventZ[KDFIXEDSPLIT_NUM]==-FLT_MAX);
}

void KDFixedSplitEstimator::addTri(int count, const AxisAlignedBox &box) {
  F32vec4 min = box.min-eps;
  F32vec4 max = box.max+eps;
  F32vec4 left = (min-bounds.min)*b;
  F32vec4 right = (max-bounds.min)*b;
  F32vec4 v_half(0.5f);
  F32vec4 zero(0.0f);
  F32vec4 limit(float(KDFIXEDSPLIT_NUM));
  //leftIndex = ceil(left), range limited to force it be within zero and KDFIXEDSPLIT_NUM
  const Is32vec4 leftIndex = RoundToIs32vec4(simd_min(simd_max(zero,left+v_half),limit));
  //rightIndex = floor(right), range limited to force it be within zero and KDFIXEDSPLIT_NUM
  const Is32vec4 rightIndex = RoundToIs32vec4(simd_min(simd_max(zero,right-v_half),limit));
  assert(leftIndex[0] <= rightIndex[0]+1);
  assert(leftIndex[1] <= rightIndex[1]+1);
  assert(leftIndex[2] <= rightIndex[2]+1);
  int leftIndex0 = leftIndex[0];
//  int leftIndex1 = leftIndex[1];
//  int leftIndex2 = leftIndex[2];
//  int leftIndex0 = ExtractWord16(leftIndex,0);
  //since indices are less than KDFIXEDSPLIT_NUM+1, they fit into a 16bit word and can be
  //extracted more quickly like this (avoids a store to offset load dependency)
  int leftIndex1 = ExtractWord2(leftIndex); 
  int leftIndex2 = ExtractWord4(leftIndex);
  int rightIndex0 = rightIndex[0];
//  int rightIndex1 = rightIndex[1];
//  int rightIndex2 = rightIndex[2];
  int rightIndex1 = ExtractWord2(rightIndex);
  int rightIndex2 = ExtractWord4(rightIndex);
  leftTriX[leftIndex0] += count;
  leftEventX[leftIndex0] = minv(leftEventX[leftIndex0],min[0]);
  leftTriY[leftIndex1] += count;
  leftEventY[leftIndex1] = minv(leftEventY[leftIndex1],min[1]);
  leftTriZ[leftIndex2] += count;
  leftEventZ[leftIndex2] = minv(leftEventZ[leftIndex2],min[2]);
  rightTriX[rightIndex0] += count;
  rightEventX[rightIndex0] = maxv(rightEventX[rightIndex0],max[0]);
  rightTriY[rightIndex1] += count;
  rightEventY[rightIndex1] = maxv(rightEventY[rightIndex1],max[1]);
  rightTriZ[rightIndex2] += count;
  rightEventZ[rightIndex2] = maxv(rightEventZ[rightIndex2],max[2]);
  totalTri += count;
}

void KDFixedSplitEstimator::addOther(int count, const AxisAlignedBox &box) {
  F32vec4 min = box.min-eps;
  F32vec4 max = box.max+eps;
  F32vec4 left = (min-bounds.min)*b;
  F32vec4 right = (max-bounds.min)*b;
  F32vec4 v_half(0.5f);
  F32vec4 zero(0.0f);
  F32vec4 limit(float(KDFIXEDSPLIT_NUM));
  //leftIndex = ceil(left), range limited to force it be within zero and KDFIXEDSPLIT_NUM
  const Is32vec4 leftIndex = RoundToIs32vec4(simd_min(simd_max(zero,left+v_half),limit));
  //rightIndex = floor(right), range limited to force it be within zero and KDFIXEDSPLIT_NUM
  const Is32vec4 rightIndex = RoundToIs32vec4(simd_min(simd_max(zero,right-v_half),limit));
  assert(leftIndex[0] <= rightIndex[0]+1);
  assert(leftIndex[1] <= rightIndex[1]+1);
  assert(leftIndex[2] <= rightIndex[2]+1);
  int leftIndex0 = leftIndex[0];
  int leftIndex1 = ExtractWord2(leftIndex);
  int leftIndex2 = ExtractWord4(leftIndex);
  int rightIndex0 = rightIndex[0];
  int rightIndex1 = ExtractWord2(rightIndex);
  int rightIndex2 = ExtractWord4(rightIndex);
  leftOtherX[leftIndex0] += count;
  leftEventX[leftIndex0] = minv(leftEventX[leftIndex0],min[0]);
  leftOtherY[leftIndex1] += count;
  leftEventY[leftIndex1] = minv(leftEventY[leftIndex1],min[1]);
  leftOtherZ[leftIndex2] += count;
  leftEventZ[leftIndex2] = minv(leftEventZ[leftIndex2],min[2]);
  rightOtherX[rightIndex0] += count;
  rightEventX[rightIndex0] = maxv(rightEventX[rightIndex0],max[0]);
  rightOtherY[rightIndex1] += count;
  rightEventY[rightIndex1] = maxv(rightEventY[rightIndex1],max[1]);
  rightOtherZ[rightIndex2] += count;
  rightEventZ[rightIndex2] = maxv(rightEventZ[rightIndex2],max[2]);
  totalOther += count;
}

void KDFixedSplitEstimator::integrateCounts() {
  int curX = 0, curY = 0, curZ = 0;
  for(int i=0;i<=KDFIXEDSPLIT_NUM;i++) {
    curX += leftTriX[i];
    curY += leftTriY[i];
    curZ += leftTriZ[i];
    leftTriX[i] = curX;
    leftTriY[i] = curY;
    leftTriZ[i] = curZ;
  }
  curX = curY = curZ = 0;
  for(int j=KDFIXEDSPLIT_NUM;j>=0;j--) {
    curX += rightTriX[j];
    curY += rightTriY[j];
    curZ += rightTriZ[j];
    rightTriX[j] = curX;
    rightTriY[j] = curY;
    rightTriZ[j] = curZ;
  }
  for(int k=0;k<=KDFIXEDSPLIT_NUM;k++) {
    assert(leftTriX[k]<=totalTri);
    assert(rightTriX[k]<=totalTri);
    assert(leftTriY[k]<=totalTri);
    assert(rightTriY[k]<=totalTri);
    assert(leftTriZ[k]<=totalTri);
    assert(rightTriZ[k]<=totalTri);
    assert(leftTriX[k]+rightTriX[k] >= totalTri);
    assert(leftTriY[k]+rightTriY[k] >= totalTri);
    assert(leftTriZ[k]+rightTriZ[k] >= totalTri);
  }

  curX = curY = curZ = 0;
  for(int i=0;i<=KDFIXEDSPLIT_NUM;i++) {
    curX += leftOtherX[i];
    curY += leftOtherY[i];
    curZ += leftOtherZ[i];
    leftOtherX[i] = curX;
    leftOtherY[i] = curY;
    leftOtherZ[i] = curZ;
  }
  curX = curY = curZ = 0;
  for(int j=KDFIXEDSPLIT_NUM;j>=0;j--) {
    curX += rightOtherX[j];
    curY += rightOtherY[j];
    curZ += rightOtherZ[j];
    rightOtherX[j] = curX;
    rightOtherY[j] = curY;
    rightOtherZ[j] = curZ;
  }
  for(int k=0;k<=KDFIXEDSPLIT_NUM;k++) {
    assert(leftOtherX[k]<=totalOther);
    assert(rightOtherX[k]<=totalOther);
    assert(leftOtherY[k]<=totalOther);
    assert(rightOtherY[k]<=totalOther);
    assert(leftOtherZ[k]<=totalOther);
    assert(rightOtherZ[k]<=totalOther);
    assert(leftOtherX[k]+rightOtherX[k] >= totalOther);
    assert(leftOtherY[k]+rightOtherY[k] >= totalOther);
    assert(leftOtherZ[k]+rightOtherZ[k] >= totalOther);
  }
  //if box is already so narrow as to approach limits of floating point resolution,
  //prevent any further splitting along that axis
  if (bounds.max[0]-bounds.min[0]<16*eps[0]) {
    for(int i=0;i<KDFIXEDSPLIT_NUM;i++) {
      leftTriX[i] = rightTriX[i] = totalTri;
      leftOtherX[i] = rightOtherX[i] = totalOther;
    }
  }
  if (bounds.max[1]-bounds.min[1]<16*eps[1]) {
    for(int i=0;i<KDFIXEDSPLIT_NUM;i++) {
      leftTriY[i] = rightTriY[i] = totalTri;
      leftOtherY[i] = rightOtherY[i] = totalOther;
    }
  }
  if (bounds.max[2]-bounds.min[2]<16*eps[2]) {
    for(int i=0;i<KDFIXEDSPLIT_NUM;i++) {
      leftTriZ[i] = rightTriZ[i] = totalTri;
      leftOtherZ[i] = rightOtherZ[i] = totalOther;
    }
  }

  //fixup events for easy access later
  for(int i=0;i<KDFIXEDSPLIT_NUM;i++) {
    leftEventX[i] = leftEventX[i+1];
    leftEventY[i] = leftEventY[i+1];
    leftEventZ[i] = leftEventZ[i+1];
  }
  leftEventX[KDFIXEDSPLIT_NUM] = minv(leftEventX[KDFIXEDSPLIT_NUM],bounds.max[0]-0.25f*eps[0]);
  leftEventY[KDFIXEDSPLIT_NUM] = minv(leftEventY[KDFIXEDSPLIT_NUM],bounds.max[1]-0.25f*eps[1]);
  leftEventZ[KDFIXEDSPLIT_NUM] = minv(leftEventZ[KDFIXEDSPLIT_NUM],bounds.max[2]-0.25f*eps[2]);
  for(int i=KDFIXEDSPLIT_NUM-1;i>0;i--) {
    leftEventX[i] = minv(leftEventX[i],leftEventX[i+1]);
    leftEventY[i] = minv(leftEventY[i],leftEventY[i+1]);
    leftEventZ[i] = minv(leftEventZ[i],leftEventZ[i+1]);
  }

  for(int j=KDFIXEDSPLIT_NUM;j>0;j--) {
    rightEventX[j] = rightEventX[j-1];
    rightEventY[j] = rightEventY[j-1];
    rightEventZ[j] = rightEventZ[j-1];
  }
  rightEventX[0] = maxv(rightEventX[0],bounds.min[0]+0.25f*eps[0]);
  rightEventY[0] = maxv(rightEventY[0],bounds.min[1]+0.25f*eps[1]);
  rightEventZ[0] = maxv(rightEventZ[0],bounds.min[2]+0.25f*eps[2]);
  for(int j=1;j<KDFIXEDSPLIT_NUM;j++) {
    rightEventX[j] = maxv(rightEventX[j],rightEventX[j-1]);
    rightEventY[j] = maxv(rightEventY[j],rightEventY[j-1]);
    rightEventZ[j] = maxv(rightEventZ[j],rightEventZ[j-1]);
  }
}

KDSplitCode KDFixedSplitEstimator::getSplitCode(int type, int index)
{
  assert( type == (type & KDST_MASK) );
  if (type==KDST_LEAF) {
    return KDSplitCode(KDST_LEAF);
  } else {
    assert((index > 0)&&(index < KDFIXEDSPLIT_NUM));
    float splitValue = (bounds.min[type]*(KDFIXEDSPLIT_NUM-index) + bounds.max[type]*index)
      * (1.0f/KDFIXEDSPLIT_NUM);
    return KDSplitCode(type,splitValue);
  }
}

KDSplitCode KDFixedSplitEstimator::getBestSplitCode(int type, int index)
{
  float splitValue;
  int leftCount,rightCount;
  switch (type) {
  case KDST_LEAF:
    return KDSplitCode(KDST_LEAF);
  case KDST_SPLIT_X:
    leftCount = getLeftTriCountX(index) + getLeftOtherCountX(index);
    rightCount = getRightTriCountX(index) + getRightOtherCountX(index);
    splitValue = (leftCount<rightCount)?getLeftEventX(index):getRightEventX(index);
    break;
  case KDST_SPLIT_Y:
    leftCount = getLeftTriCountY(index) + getLeftOtherCountY(index);
    rightCount = getRightTriCountY(index) + getRightOtherCountY(index);
    splitValue = (leftCount<rightCount)?getLeftEventY(index):getRightEventY(index);
    break;
  case KDST_SPLIT_Z:
    leftCount = getLeftTriCountZ(index) + getLeftOtherCountZ(index);
    rightCount = getRightTriCountZ(index) + getRightOtherCountZ(index);
    splitValue = (leftCount<rightCount)?getLeftEventZ(index):getRightEventZ(index);
    break;
  default:
    BRITE_DEBUGBREAK;
	splitValue = 0.0f;	// Just to make the compiler happy
  }
  assert(splitValue>bounds.min[type]);
  assert(splitValue<bounds.max[type]);
//  float relPos = (splitValue-bounds.min[type])/(bounds.max[type]-bounds.min[type]);
  return KDSplitCode(type,splitValue);
}


